package com.example.leetcode.leetcode.hot100;

import com.example.leetcode.leetcode.tree.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;

public class Solution114 {

    public void flatten(TreeNode root) {
        Deque<TreeNode> queue = new ArrayDeque<>();
        dfs(root, queue);
        TreeNode p = queue.poll();
        while(!queue.isEmpty()){
            p.right =queue.poll();
            p.left = null;
            p = p.right;
        }
    }

    public void dfs(TreeNode root, Deque<TreeNode> queue) {
        if (root == null) {
            return;
        }
        queue.addLast(root);
        if (null != root.left) {
            dfs(root.left, queue);
        }
        if (null != root.right) {
            dfs(root.right, queue);
        }
    }

    public static void main(String[] args) {
        Solution114 solution114 = new Solution114();
        TreeNode root =new TreeNode(1);
        TreeNode rl =new TreeNode(2);
        TreeNode rr =new TreeNode(5);
        root.left = rl;
        root.right = rr;
        TreeNode rll =new TreeNode(3);
        TreeNode rlr =new TreeNode(4);
        rl.left = rll;
        rl.right = rlr;
        TreeNode rrr =new TreeNode(6);
        rr.right = rrr;
        solution114.flatten(root);
    }
}
